package com.sort;


import java.util.Arrays;

/**
 * @className: com.sort.QuickSort
 * @description: 快速排序
 * @author: tong.li
 * @createTime: 2023/2/22 9:47
 * @copyright: Tongcheng-Elong Holdings Limited
 */
public class QuickSort {

    public static void main(String[] args) {
        // int[] arr = {6, 1, 3, 7, 9, 3, 4,5,8};
        int[] arr = {6, 5, 8, 1, 9, 3, 2};
        System.out.println("排序前:" + Arrays.toString(arr));
        sort(arr);
        System.out.println("排序后:" + Arrays.toString(arr));

    }

    /**
     * 整个数组排序
     * @param arr
     */
    public static void sort(int[] arr) {
        int low = 0, high = arr.length -1;
        sort(arr, low, high);
    }

    /**
     * 实际排序方法
     * @param arr
     * @param low
     * @param high
     */
    private static void sort(int[] arr, int low, int high) {
        if (low >= high) {
            return;
        }
        // 扫描交换并返回基准值的索引
        int baseIdx = part(arr, low, high);
        // 递归处理左子组和右子组
        sort(arr, low, baseIdx -1);
        sort(arr, baseIdx + 1, high);
    }

    /**
     * 分区
     * @param arr
     * @param low
     * @param high
     */
    public static int part(int[] arr, int low, int high) {
        // 先找基准,再定一个两个扫描指针
        int baseValue = arr[low], left = low, right = high + 1;
        while (true) {
            // 先从右边扫描，找个比基准值要小的
            while (compare(baseValue, arr[--right])) {
                if (right == low) {
                    break;
                }
            }
            // 从左边扫，找个比基准值大的
            while (!compare(baseValue, arr[++left])) {
                if (left == high) {
                    break;
                }
            }
            if (left >= right) {
                break;
            }
            // 交换
            swap(arr, left, right);
        }
        // 基准值归位
        swap(arr, low, right);
        return right;
    }


    /**
     * 交换
     * @param arr
     * @param start
     * @param end
     */
    public static void swap(int[] arr, int start, int end) {
        int tmp = arr[start];
        arr[start] = arr[end];
        arr[end] = tmp;
    }


    public static boolean compare(int value1, int value2) {
        return  value1 < value2;
    }



}
